package 马踏棋盘;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.Stack;

public class 马踏棋盘 {
	Horse horse;

	public static void main(String args[]) {
		马踏棋盘 toDo = new 马踏棋盘();
		Scanner s = new Scanner(System.in);
		System.out.print("请输入起点坐标:");
		//toDo.horse = new Horse(new Location(s.nextInt() - 1, s.nextInt() - 1));
		toDo.horse = new Horse(new Location(5, 5));

		s.close();
		int Nf = (int) Math.pow(Board.getN(), 2);
		while (true) {
			if (toDo.horse.stack.isEmpty()) {
				System.out.println("无法走完");
				System.exit(0);
			}
			if (!toDo.horse.toLocation(toDo.horse.stack.peek())) {
				continue;
			}
			if (Horse.getStep() >= Nf)
				break;
			// toDo.horse.board.Print();
			// System.out.println("\n");
			if (!toDo.tryToDo()) {
				toDo.horse.backLocation();
			}
		}
		System.out.println("完成");
		toDo.horse.board.Print();
	}

	public boolean tryToDo() {
		Location[] locations = new Location[8];
		for (int i = 0; i < 8; i++) {// 生成8个方向
			locations[i] = horse.NextLocation(i);
		}
		//排序
		Arrays.sort(locations, new MyComp());
		int i;
		for (i = 0; i < 8 && locations[i] != null; i++) {
			if (locations[i] != null) {
				horse.stack.push(locations[i]);
			}
		}
		return i > 0;
	}
}

class MyComp implements Comparator<Location> {

	@Override
	public int compare(Location o1, Location o2) {
		// TODO Auto-generated method stub
		if (o1 == null && o2 == null)  return 0;
		else if(o1 == null)  return 1;
		else if(o2 == null) return -1;
		return o2.getNextNum() - o1.getNextNum();
	}

}

class Direction {// 描述8个方向
	private static int[] x = new int[] { 1, 1, 2, 2, -1, -1, -2, -2 };
	private static int[] y = new int[] { 2, -2, 1, -1, 2, -2, 1, -1 };

	public static int getX(int index) {
		return x[index];
	}

	public static int getY(int index) {
		return y[index];
	}
}

class Board {
	private static int[][] Board;
	static int nn;// 棋盘宽度

	public Board(int n) {
		nn = n;
		Board = new int[nn][nn];
	}

	public static int[][] getBoard(){
		return Board;
	}

	public void setBoard(int[][] board) {
		Board = board;
	}

	public static int getN() {
		return nn;
	}

	public static boolean isVisit(Location location) {
		if (Board[location.getX()][location.getY()] == 0)
			return false;
		return true;
	}

	public boolean toThisPoint(Location location) {// 在棋盘某一位置写上到达次序
		if (Board[location.getX()][location.getY()] != 0)
			return false;
		
		Horse.stepAdd(1);
		Board[location.getX()][location.getY()] = Horse.getStep();
		return true;
	}

	public void liveThisPoint(Location location) {
		Board[location.getX()][location.getY()] = 0;
	}

	public void Print() {
		for (int i = 0; i < nn; i++) {
			for (int j = 0; j < nn; j++) {
				System.out.printf("%02d  ", Board[i][j]);
			}
			System.out.println();
		}
	}
	/*
	 * public void setN(int n) { this.n = n; }
	 */

}

class Location {
	private int x;
	private int y;
	private int nextNum = 0;

	Location(int x, int y) {
		this.x = x;
		this.y = y;

		// 计算这个位置下一步可以走的位置
		for (int i = 0; i < 8; i++) {
			x = this.x + Direction.getX(i);
			y = this.y + Direction.getY(i);
			if (x >= 0 && x < Board.nn && y >= 0 && y < Board.nn
					&& !Board.isVisit(new Location(this.x, this.y, true))) {
				nextNum++;
			}
		}
	}

	Location(int x, int y, boolean b) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

	public int getNextNum() {
		return nextNum;
	}

	public void setNextNum(int nextNum) {
		this.nextNum = nextNum;
	}

}

class Horse {
	Board board;
	private Location CurLocation;// 马的当前位置
	// private Location[] NextLocation;//马下一步可以走的方向
	Stack<Location> stack;// 马准备走的位置
	private static int step = 0;

	public Location NextLocation(int index) {
		int x = this.CurLocation.getX() + Direction.getX(index);
		int y = this.CurLocation.getY() + Direction.getY(index);
		if (x >= 0 && x < Board.nn&& y >= 0 && y < Board.nn && !Board.isVisit(new Location(x, y))) {
			Location NextLocation = new Location(x, y);
			return NextLocation;
		}
		return null;
	}

	public static int getStep() {
		return step;
	}

	public static void stepAdd(int num) {
		step += num;
	}

	public Location getCurLocation() {
		return CurLocation;
	}

	public boolean toLocation(Location curLocation) {
		this.CurLocation = curLocation;
		if (!this.board.toThisPoint(getCurLocation())) {
			backLocation();
			return false;
		}
		
		return true;
	}

	public void backLocation() {
		stack.pop();
		stepAdd(-1);
		this.board.liveThisPoint(getCurLocation());

	}

	Horse(Location InitLocation) {
		stack = new Stack<Location>();
		board = new Board(8);//棋盘大小为8
		stack.push(InitLocation);// 将起点压入待走栈
	}

}
